The location of a device may be determined using a global positioning system (“GPS”). In a general GPS system, a receiver acquires signals from four or more satellite vehicles to obtain a three dimensional location and a time stamp. A receiver may employ multiple channels and the received signal in each channel may be used to acquire a signal from a single signal source. After acquisition, a delay-locked loop is traditionally used to track the signal source and is used to give updates to the receiver position through time. GPS satellite vehicles emit two microwave carrier signals of L1 and L2 frequency. The two microwave carrier signals are modulated by: 1) a C/A code (Coarse Acquisition), 2) a P-Code (Precise), and 3) a data message.
The C/A code is a repeating 1 MHz Pseudo Random Noise (PRN) code that modulates the signal at frequency L1. The C/A PRN code comprises 1023 chips that repeat every millisecond. There is a different C/A PRN code for each GPS satellite vehicle. The P-Code modulates the signals at both the L1 and L2 frequencies. The P-Code is a 10 MHz PRN code. The data message modulates the L1-C/A code signal. The data message is a 50 Hz signal consisting of data bits, also known as “navigation bits”, that give a time stamp, the GPS satellite vehicle orbits, clock corrections, and other parameters. All of this data is useful for the receiver to know in order to calculate and update its position. In traditional GPS systems, this data is decoded from the signal after the signal has been acquired and acquisition is carried out without the benefit of knowing this data.
In one approach, a receiver may attempt to acquire a signal by: 1) generating a replica of the PRN code emitted by a satellite vehicle that is potentially visible overhead the receiver, and 2) determining a correlation between the received signal and a suitable modulated replica code. Typically, the correlation between the received signal and the replica code is performed by calculating the In Phase (“I”) and Quadrature (“Q”) correlation integrals.
The uncertainty in the carrier modulation frequency arises from two primary sources. The first is the net movement of the individual signal source relative to the receiver. In the case of GPS, the signal source is a satellite moving at a speed of a few thousand meters every second while the receiver may also be moving at a usually slower but usually unknown speed. In the case of GPS, the velocity of the satellite may be calculated to very high accuracy by the receiver once it has access to the current orbital parameters of the satellite in question and the current time. The motion of the signal source and the motion of the receiver introduce a Doppler shift that effectively compresses or dilates the signal in time, resulting in a change in modulation frequency as well. The second major source of frequency uncertainty is the imperfect syntony between the clock on the receiver and the clock in the signal source. Since the signal source clock and the receiver clock are generally distinct, there is a net slowing-down or speeding-up of time between the signal source and the receiver. This clock drift of the receiver relative to the source is also experienced as a compression or dilation of the signal at the receiver and is herein referred to as “clock Doppler.”
In addition to the frequency uncertainty, there is an uncertainty introduced due to the unknown propagation delay from the signal source to the receiver. The speed of light is finite and hence it takes a finite time proportional to the distance between the source and the receiver for the signal to arrive at the receiver after being transmitted at the source.
The initial problem of acquiring a signal therefore involves a search over the exact modulation frequency and the delay to the signal source. The pseudorandom structure underlying the signal ensures that the magnitude of the correlation integrals will be relatively small if either the modulation frequency or the delay is substantially different from the true value. Finally, the repeating nature of the PRN code implies that the delay value provides range information only modulo the time of repetition, unless a priori knowledge about the data bits is used.
In traditional positioning systems, the problem of acquisition is solved mostly independently for the different signal sources. Each channel successively tests different delay and frequency hypotheses, and computes I and Q correlations for them. When a sufficiently high value is found, it is tracked for a while and the receiver attempts to decode the data bits. Different channels may be allocated to search for different signal sources, but there is no substantial interaction between the different searches during the acquisition phase. A significant disadvantage of the above approach to acquisition is that it might have to search for a long amount of time before it has acquired enough signals to proceed. The longer the duration of coherent integration, the more finely the modulation frequency has to be known. The more attenuated the signal, the longer the duration of computing the correlations at any given frequency and delay pair must be before the signal can be discriminated from the noise. These two problems combine to make search in attenuated environments prohibitively expensive in terms of either required delays or the number of independent channels needed to acquire the signals. Furthermore, the independence of the channels for each signal in the acquisition phase does not leverage the calculations for the clock Doppler and delay values performed with respect to one signal source to aid the calculations with respect to another signal source.
After acquisition, in traditional GPS, the distance to each satellite is estimated by decoding the time stamp information embedded in the data message and comparing it to the time of reception by the receiver's own clock. The result of this comparison is traditionally referred to as a “pseudorange” and is expressed in meters rather than seconds by multiplying by the speed of light. Any net drift due to the imperfect synchronization of the two clocks is corrected for through a space/time triangulation procedure combining the pseudoranges from four or more signal sources. This procedure also results in an initial position estimate. This estimate is then updated through time using the outputs of delay locked loops tracking the received signals. This approach suffers from the drawback of having to wait for the time-stamp in the data message before giving even an initial position fix. In traditional GPS, the time stamps are transmitted only once every few seconds. This means that even if the receiver is able to acquire all the satellites instantly, it still might have to wait up to a few seconds before being able to give any position estimate at all.
Some of these difficulties are partially mitigated by the techniques of assisted GPS but many of them remain problematic, especially in challenging attenuated environments such as urban buildings. In such environments, the traditional assisted GPS technologies become impractical due to the computation expense and/or the for very long sampling times.
Our earlier U.S.A. patent applications entitled “SIGNAL ACQUISITION USING DATA BIT INFORMATION” (Ser. No. 09/888,228 filed Jun. 22, 2001. Hereafter referred to as Application 228) which is expressly incorporated herein by reference, “SYNTHESIZING COHERENT CORRELATION SUMS AT ONE OR MULTIPLE CARRIER FREQUENCIES USING CORRELATION SUMS CALCULATED AT A COARSE SET OF FREQUENCIES” (Ser. No. 09/888,227 filed Jun. 22, 2001. Hereafter referred to as Application 227) which is expressly incorporated herein by reference, “EXTRACTING FINE-TUNED ESTIMATES FROM CORRELATION FUNCTIONS EVALUATED AT LIMITED NUMBER OF VALUES” (Ser. No. 09/888,338 filed Jun. 22, 2001. Hereafter referred to as Application 338) which is expressly incorporated herein by reference “DETERMINING THE SPATIO-TEMPORAL AND KINEMATIC PARAMETERS OF A SIGNAL RECEIVER AND ITS CLOCK BY INFORMATION FUSION” (Ser. No. 09/888,229 filed Jun. 22, 2001. Hereafter referred to as Application 229) which is expressly incorporated herein by reference, and “DETERMINING LOCATION INFORMATION USING SAMPLED DATA CONTAINING LOCATION-DETERMINING SIGNALS AND NOISE”, (Ser. No. 09/888,337 filed Jun. 22, 2001. Hereafter referred to as Application 337) which is expressly incorporated herein by reference, disclosed new techniques that dramatically reduced computational burdens. However, the techniques described explicitly there generally operate with an integer number of milliseconds as the smallest sized data chunks for processing. If the frequency uncertainty were large, the traditional solution of redoing the calculations using many disjoint smaller frequency ranges spanning the original larger frequency range would have to be utilized. This introduces a computational slowdown that is roughly linear in the large frequency uncertainty. In some practical situations, the slowdown may be as large as a factor of four or more.
Therefore, there is clearly a need for a faster approach that is less impacted computationally by the size of the frequency uncertainty, when this uncertainty is large.